package com.yuren.codecrushlearn.Q5400;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with Intellij IDEA.
 * Description:
 * <p>
 * 5451. 邻接表的实现
 * 邻接表是图的一种存储方式。邻接表由图的顶点和边组成。
 * 图的顶点是图的基本组成部分，边则是顶点之间的连接。
 * 邻接表的实现方式是将每个顶点的邻接点存储在一个链表中。
 * 邻接表的实现方式有两种：一种是数组实现，一种是链表实现。
 * 数组实现的邻接表的时间复杂度为O(V+E)，其中V是顶点数，E是边数。
 * 邻接表的实现方式可以用于解决图的遍历、最短路径、最小生成树等问题。
 *
 * @author 10204
 * @date 2025-06-09 23:53
 */
public class Q5451 {
    private int v;
    private final int[][] matrix;

    public Q5451(int v) {
        this.v = v;
        this.matrix = new int[v][v];
        for (int i = 0; i < v; i++) {
            Arrays.fill(this.matrix[i], Integer.MAX_VALUE);
        }

    }

    public void addEdge(int v1, int v2, int weight) {
        matrix[v1][v2] = weight;
    }

    public int getEdgeWeight(int v1, int v2) {
        if (matrix[v1][v2] == Integer.MAX_VALUE) {
            return -1;
        }
        return matrix[v1][v2];
    }

    public List<Integer> getAdjacentVertices(int v1) {
        List<Integer> res = new ArrayList<>();
        for (int j = 0; j < matrix[v1].length; j++) {
            if (matrix[v1][j] != Integer.MAX_VALUE) {
                res.add(j);
            }
        }
        return res;
    }
}
